#include<iostream>
#include "include/ObjectPool.h"
#include <unordered_map>
#include <ctime>
using namespace std;
    
#define CHECK_BITS(key,pos) ((((unsigned int)(key))<<sizeof(key)*8-((pos)+1)*BITS)>>(sizeof(key)*8-BITS))

template<int BITS, typename value_type>
struct radixNode{
    radixNode* child[1<<BITS];
    value_type value;
    radixNode(){
        for(int i = 0; i < (1<<BITS); i++){
            child[i] = nullptr;
        }
        value = 0;
    }
};

template<int BITS, typename key_type, typename value_type>
class radixTree{
private:
    radixNode<BITS, value_type>* root;
    ObjectPool<radixNode<BITS, value_type>> pool;
    enum {HEIGHT = sizeof(key_type) * 8 / BITS};
    void delNode(radixNode<BITS, value_type>* p){
        for(int i = 0; i < (1<<BITS); i++){
            if(p->child[i]){
                delNode(p->child[i]);
            }
        }
        pool.Delete(p);
    }
public:
    radixTree(){
        root = pool.New();
        for(int i = 0; i < (1<<BITS); i++){
            root->child[i] = nullptr;
        }
    }
    ~radixTree(){
        // delNode(root);
    }

    value_type* find(key_type key){
        radixNode<BITS, value_type>* p = root;
        int i = 0;
        while(p && i < HEIGHT){
            p = p->child[CHECK_BITS(key, i)];
            i++;
        }
        if(p){
            return &p->value;
        }else{
            return nullptr;
        }
    }

    void insert(key_type key, value_type value){
        radixNode<BITS, value_type>* p = root;
        int i = 0;
        while(i < HEIGHT){
            int index = CHECK_BITS(key, i);
            if(p->child[index] == nullptr){
                p->child[index] = pool.New();
            }
            p = p->child[index];
            i++;
        }
        p->value = value;
    }

    void erase(key_type key){
        radixNode<BITS, value_type>* p = root;
        radixNode<BITS, value_type>* parent = nullptr;
        int i = 0;
        while(p && i < HEIGHT){
            int index = CHECK_BITS(key, i);
            parent = p;
            p = p->child[index];
            i++;
        }
        if(p){
            pool.Delete(p);
            parent->child[CHECK_BITS(key, i-1)] = nullptr;
        }
    }
};

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <functional>
using namespace std;
 
// 自定义的哈希函数类
class HashFunc{
public:
	int operator()(const int key){//对于int类型的key对应的hash函数，随便编的，不要在意这些细节
		return 3 * key + 1;
	}
    unsigned long long operator()(const unsigned long long key){
        return key;
    }
};
 
template <typename Key, typename Value>//这是链表节点，包括key和value
class HashNode{
public:
	Key key;
	Value value;
	HashNode *next;
	HashNode(Key _key, Value _value) :key(_key), value(_value), next(NULL){}
	~HashNode(){}
};
 
template <typename Key, typename Value, typename HashFunc>
class HashMap{
public:
	int size;
	HashFunc hash;//hash是自定义的哈希函数，重载了类的()相当于重新定义了一个函数
	HashNode<Key, Value>**table;
	Value valuenull = 0;
 
	HashMap(int _size = 10000);
	~HashMap();
	//插入操作
	bool insert(Key key, Value value);
	//删除操作
	bool del(Key &key);
	//查找，下面的[]运算符重载与之功能相同
	Value &find(const Key &key);
	Value &operator[](const Key &key);
	void print();//打印
 
};
 
template <typename Key, typename Value, typename HashFunc>
HashMap<Key, Value, HashFunc>::HashMap(int _size) :size(_size),hash(){
	//对table初始化
	table = new HashNode<Key, Value>*[_size];
	for (int i = 0; i < _size; i++){
		table[i] = NULL;
	}
}
 
template<typename Key, typename Value, typename HashFunc>
HashMap<Key, Value, HashFunc>::~HashMap(){
	for (int i = 0; i < size; i++){
		HashNode<Key, Value>* cur = table[i];
		while (cur){
			HashNode<Key, Value>*temp = cur;
			cur = cur->next;
			delete temp;
			temp = NULL;
		}
	}
	delete[] table;
}
 
template<typename Key, typename Value, typename HashFunc>
bool HashMap<Key, Value, HashFunc>::insert(Key key, Value value){//增加一个key-value对
	int index = hash(key) % size;//求出来对于每个key哈希到的地址索引
	HashNode<Key, Value> *hnode = new HashNode<Key, Value>(key, value);
	hnode->next = table[index];
	table[index] = hnode;
	return true;
}

template<typename Key, typename Value, typename HashFunc>
Value &HashMap<Key, Value, HashFunc>::find(const Key &key){
	int index = hash(key) % size;
	if (table[index] == NULL) return valuenull;
	HashNode<Key, Value>* cur = table[index];
	while (cur){
		if (cur->key == key) return cur->value;
		else cur = cur->next;
	}
	return valuenull;
}
 
template<typename Key, typename Value, typename HashFunc>
Value &HashMap<Key, Value, HashFunc>::operator[](const Key &key){
	Value &value = find(key);
    if(value == valuenull){
        insert(key, 0);
        return find(key);
    }else{
        return value;
    }
}


int main(){
    size_t start = clock();
    // radixTree<3, unsigned int, int> tree;
    // for(int i = 0; i < 1000000; i++){
    //     tree.insert(i, i);
    // }
    // for(int i = 0; i < 1000000; i++){
    //     int* p = tree.find(i);
    //     if(p == nullptr || *p != i){
    //         std::cout << "error" << std::endl;
    //     }
    // }
    size_t end = clock();
    // std::cout << "time: " << end - start << std::endl;

    start = clock();
    unordered_map<unsigned long long, int> map;
    for(int i = 0; i < 1000000; i++){
        map[i] = i;
    }
    for(int i = 0; i < 1000000; i++){
        if(map[i] != i){
            std::cout << "error" << std::endl;
        }
    }
    end = clock();
    std::cout << "time: " << end - start << std::endl;

    start = clock();
    HashMap<unsigned long long, int, HashFunc> hashmap(100000);
    for(int i = 0; i < 1000000; i++){
        hashmap[i] = i;
    }
    for(int i = 0; i < 1000000; i++){
        if(hashmap.find(i) != i){
            std::cout << "error" << std::endl;
        }
    }
    std::cout << hashmap.find(10000000) << std::endl;
    end = clock();
    std::cout << "time: " << end - start << std::endl;
}